package Sudoku;

import static org.junit.Assert.assertEquals;


import java.awt.Color;
import java.awt.event.ActionEvent;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;

import javax.swing.BorderFactory;
import javax.swing.JButton;

import org.junit.Test;

import acm.gui.IntField;
import acm.gui.TableLayout;
import acm.gui.TablePanel;
import acm.program.Program;

public class Sudoku extends Program {

	// the model of the game board
	IntField[][] board;

	/**
	 * Construct a new game of Sudoku.
	 * 
	 * Initializes the game board with all zeroes.
	 */
	public Sudoku() {
		super();
		board = new IntField[9][9];
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				board[i][j] = new IntField(0);
			}
		}
	}

	/**
	 * Initialize a new game of Sudoku with a given configuration.
	 * 
	 * @param values
	 *            The configuration of the game board.
	 */
	public Sudoku(int[][] values) {
		this();
		setConfiguration(values);
	}

	/**
	 * Initialize the view component.
	 */
	@Override
	public void init() {
		setTitle("Sudoku");
		setLayout(new TableLayout(4, 3));
		for (int i = 0; i < 9; i++) {
			add(assembleInnerTable(i));
		}
		add(new JButton("Solve"));
		addActionListeners();
	}

	/**
	 * Assemble a single 3x3 field.
	 * 
	 * @param n
	 *            The number of the 3x3 field to assemble a table component for.
	 * @return The TablePanel containing a 3x3 field.
	 */
	private TablePanel assembleInnerTable(int n) {
		TablePanel tp = new TablePanel(3, 3);
		for (int i = 0; i < 9; i++) {
			// we assemble 3x3 field-wise and have to adjust array indices
			// accordingly
			int row = 3 * (n / 3) + i / 3;
			int col = 3 * (n % 3) + i % 3;

			// The constructor made sure these are instantiated IntFields
			IntField intField = board[row][col];

			// Register a KeyListener to suppress non-digit entries
			intField.addKeyListener(new KeyListener() {
				@Override
				public void keyPressed(KeyEvent e) {
					// don't care
				}

				@Override
				public void keyReleased(KeyEvent e) {
					// don't care
				}

				@Override
				public void keyTyped(KeyEvent e) {
					try {
						// try to parse the pressed keys value into an Integer
						Integer.parseInt(String.valueOf(e.getKeyChar()));
					} catch (NumberFormatException nfe) {
						// consume the event and stop it from propagating
						e.consume();
					}
				}
			});
			tp.add(intField);
		}
		// draw a solid black border around every 3x3 field
		tp.setBorder(BorderFactory.createLineBorder(Color.black));
		return tp;
	}

	/**
	 * Initialize the game board with the given arrays of ints.
	 * 
	 * @param init
	 *            The 9x9 two-dimensional array with int values from 0..9
	 */
	public void setConfiguration(int[][] init) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (init[i][j] > 0 && init[i][j] <= 9) {
					board[i][j].setValue(init[i][j]);
				} else {
					board[i][j].setValue(0);
				}
			}
		}
	}

	/**
	 * Return the current configuration of the game board.
	 * 
	 * @return The current configuration.
	 */
	public int[][] getConfiguration() {
		int[][] tmp = new int[9][9];
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				tmp[i][j] = board[i][j].getValue();
			}
		}
		return tmp;
	}

	// if no solution was found, color every field red
	public void colorForFailure() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				board[i][j].setBackground(new Color(255, 0, 0));
			}
		}
	}

	// if there was a solution, color the new values fields green
	public void colorForSuccess(int[][] solution) {
		int[][] actual = getConfiguration();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (solution[i][j] != actual[i][j]) {
					board[i][j].setBackground(new Color(0, 255, 0));
					board[i][j].setValue(solution[i][j]);
				} else {
					board[i][j].setBackground(new Color(255, 255, 255));
				}
			}
		}
	}

	/**
	 * The ActionListeners method to process pressed buttons.
	 */
	@Override
	public void actionPerformed(ActionEvent e) {
		if (e.getActionCommand().equals("Solve")) {
			// The solve button was pressed, find a solution
			int[][] solution = solve(getConfiguration());
			if (solution != null) {
				colorForSuccess(solution);
			} else {
				colorForFailure();
			}
		}
	}

	/**
	 * Solve the given Sudoku configuration and return the result.
	 * 
	 * @param configuration
	 *            A 9x9 two-dimensional array, columns first.
	 * @return The solution for this game of Sudoku.
	 */
	public int[][] solve(int[][] configuration) {
		// TODO please implement this method!
		return solve(configuration, getNextFreeField(configuration));
		//return new int[9][9];
	}

	public static void main(final String[] args) {
		final int[][] emptyField = new int[][] { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

		final int[][] fullField = new int[][] { { 5, 3, 4, 6, 7, 8, 9, 1, 2 },
				{ 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 9, 8, 3, 4, 2, 5, 6, 7 },
				{ 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 4, 2, 6, 8, 5, 3, 7, 9, 1 },
				{ 7, 1, 3, 9, 2, 4, 8, 5, 6 }, { 9, 6, 1, 5, 3, 7, 2, 8, 4 },
				{ 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 9 } };

		final int[][] actualField1 = new int[][] {
				{ 5, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
				{ 0, 9, 8, 0, 0, 0, 0, 6, 0 }, { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
				{ 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
				{ 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
				{ 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

		final int[][] actualField2 = new int[][] {
				{ 1, 0, 2, 0, 0, 0, 0, 0, 0 }, { 0, 0, 3, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 0, 0, 4 }, { 0, 4, 0, 0, 5, 0, 0, 0, 0 },
				{ 0, 6, 0, 0, 7, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 2, 0 },
				{ 0, 8, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 0, 0, 0, 0, 8, 0, 0 } };

		//new Sudoku(actualField1).start();
		Sudoku a=new Sudoku();
		System.out.println(a.solve(actualField1));
	}

//	/**
//	 * Reject Configuration if it breaks at least one rule.
//	 * 
//	 * @param Configuration
//	 *            Array
//	 * @return whether configuration is ok or not.
//	 */
//
//	public static boolean reject(int[][] conf) {
//		int[] rows = new int[9], cols = new int[9], blocks = new int[9];
//		for (int i = 0; i < 9; i++) {
//			for (int j = 0; j < 9; j++) {
//				rows[i] = conf[i][j];
//				cols[i] = conf[j][i];
//				blocks = get3by3(conf, j);
//			}
//			// check rows
//			if (hasDublicate(rows) || hasDublicate(cols)
//					|| hasDublicate(blocks))
//				return false;
//		}
//		return true;
//
//	}
//
//	private static int[] get3by3(int[][] conf, int number) {
//		int[] ret = new int[9];
//		// get row of 3x3 block by %3 and col by /3.
//		// As we choose between block 1-9 we need to format a and b to be usable
//		// by for-loops
//		int a = ((number % 3) - 1) * 3;
//		int b = (number / 3) * 3;
//		int count = 0;
//
//		// convert 3x3 block to flat int[]
//		for (int i = a; i < a + 3; i++) {
//			for (int j = b; j < b + 3; j++) {
//				ret[count++] = conf[i][j];
//			}
//		}
//		return ret;
//
//	}
//
//	private static boolean hasDublicate(int[] part) {
//		HashSet set = new HashSet(9);
//		for (int i = 0; i < part.length; i++) {
//			if (!set.add(part[i]))
//				return false;
//
//		}
//		return true;
//	}
	
//	public static int getNextFreeField(int[][] conf) {
//		for(int i = 0; i<9;i++) {
//			for(int j = 0; j<9;j++) {
//				if(conf[j][i] == 0) {
//					return 9*i+j;
//				}
//			}
//		}
//		return -1;
//	}

    public boolean reject(int[][] currArray){

		//checks rows and columns
		for (int row=0; row<9; row++){			
			for (int col=0; col<9;col++){
				if (currArray[row][col] != 0) {
					for (int compRow=0; compRow<row; compRow++){
						if (currArray[row][col] == currArray[compRow][col])   
							return  true;}	
					for (int compCol=0; compCol<col; compCol++){	
						if (currArray[row][col] == currArray[row][compCol])   
							return  true;}	
				}}}


		//checks blocks
		//9 blocks:
		for(int i=0; i<3; i++){
			for(int j=0; j<3; j++){  
				//get all cells:
				for (int row=i*3; row<(i+1)*3; row++){			
					for (int col=j*3; col<(j+1)*3; col++){  
						if (currArray[row][col] != 0) {
							//get other cells:
							for (int compRow=i*3; compRow<=row; compRow++){
								for (int compCol=j*3; compCol<col; compCol++){	
									//compare 
									if (currArray[row][col] == currArray[compRow][compCol])
										return true; }}
							
							for (int rowsLastCol=0; rowsLastCol<row; rowsLastCol++){
								if (currArray[row][col] == currArray[rowsLastCol][col])
									return true;}
						}}}}}



		return false;
		
	}

	public static int getNextFreeField(int[][] matrix){
		int n=0;
			for(int p=0; p<9;p++){
		    for(int q=0;q<9;q++){
		    	 n++;
		    	 if (matrix[p][q]==0){return n-1;}
		    }}
	  return -1;
	}

	
	
	int[][] getNextExtension(int[][] currArray, int position){
		//invalid position
		if (position<0||position>80) return null;
		
		
	    int[][] newField = new int[9][9];
	    for (int i=0; i<9; i++)
	    	for(int j=0;j<9;j++)
	    		newField[i][j]=currArray[i][j];  //wichtig, sonst geht alles kaputt!!

		int row = position / 9;
		int col = position % 9;
		if (newField[row][col]<9) { 
			    newField[row][col]++;
			    return newField;}
		else
			// invalid value
			return null; 
		}
		

	
	int[][] newmat = new int[9][9];	
	
	public int[][] solve(int[][] matrix, int a) {
		
		
		
		
		
		if (getNextExtension(matrix, a) == null)
			solve(matrix, getNextFreeField(matrix));
		else
		newmat = getNextExtension(matrix, a);
		if (reject(newmat))
			solve(newmat, a);

		if (getNextFreeField(newmat) == -1)
			return newmat;
		else
			solve(newmat, getNextFreeField(newmat));
      return newmat;
	}

}